剑指 Offer 42. 连续子数组的最大和

发表于 | 分类于
没错我写点easy题找找自信了

剑指 Offer 42. 连续子数组的最大和

用时 10min

很容易看出来是用动态规划

求数组长度的最大连续子数组和，可以拆成求[ 0… n] 最大连续子数组和的子问题

状态转移方程 dpn 取决于 dp n - 1 是否为正

很明显如果 dp n - 1 为负，后面的 dp 是不用考虑它的

最后找到数组中的最大 dp 即可

1
2
3
4
5
6
7
8
9
10
11
var maxSubArray = function (nums) {
  var dp = new Array(nums.length);
  for (let i = 0; i < nums.length; i++) {
    if (i === 0) {
      dp[i] = nums[0];
    } else {
      dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
    }
  }
  return Math.max(...dp);
};